
import math
import numpy as np

def power_of_2(n):
    start = 1
    flag = False
    while start <= n:
        if start == n: flag = True
        start *= 2
    return flag

def power2_zero(n):
    if n == 0: return True
    start = 1
    flag = False
    while start <= n:
        if start == n: flag = True
        start *= 2
    return flag

def chose_server_map(gpu_index_list, server_size = 8):
    server_num_map = {}
    for gpu_id in gpu_index_list:
        server_id = int(gpu_id/8)
        if server_id not in server_num_map:
            server_num_map[server_id] = 0
        server_num_map[server_id] += 1
    return server_num_map

def find_first_element_list(pair_list, second_value):
    result = []
    for temp_pair in pair_list:
        if temp_pair[1] == second_value:
            result.append(temp_pair[0])
    return result

def find_closest_first_list_pair(pair_list, second_value):
    result_index = -1
    cur_gap = 10000000
    for temp_pair in pair_list:
        if temp_pair[1]-second_value>=0 and temp_pair[1]-second_value<cur_gap:
            cur_gap = temp_pair[1]-second_value
            result_index = temp_pair[0]
    assert result_index != -1
    assert cur_gap != 0
    return [result_index, second_value+cur_gap]

def get_leaf_module_id(leaf_id, gpu_num):
        return leaf_id+gpu_num

def get_spine_module_id(spine_id, gpu_num, leaf_num):
    return spine_id+gpu_num+leaf_num

    
            # while(len(choosed_spine_group_pair_list)>0):
            #     assert choosed_spine_group_pair_list[0][1] == choosed_spine_group_pair_list[1][1]
            #     final_target_spine_index = choosed_spine_group_pair_list[1][0]
            #     if choosed_spine_group_pair_list[0][0] not in group_migration_map:
            #         group_migration_map[choosed_spine_group_pair_list[0][0]] = {}
            #     if choosed_spine_group_pair_list[1][0] not in group_migration_map[choosed_spine_group_pair_list[0][0]]:
            #         group_migration_map[choosed_spine_group_pair_list[0][0]][choosed_spine_group_pair_list[1][0]] = []
            #     group_migration_map[choosed_spine_group_pair_list[0][0]][choosed_spine_group_pair_list[1][0]].append(choosed_spine_group_pair_list[0][1])
            #     del choosed_spine_group_pair_list[0]
            #     # 每一次都选取两个最小的group进行合并，即将其中一个spine中大小之和为n的任务迁移到另一个spine中大小为n的group中运行
            #     choosed_spine_group_pair_list.sort(key=lambda x: x[1],reverse=False)

        
if __name__ == "__main__":
    #  while(temp_require_leaf_num>=1):
    #         temp_require_spine_num = int(gpu_num/temp_require_leaf_num)
    #         # temp_require_gpu_per_leaf = int(gpu_num/temp_require_leaf_num)
    #         # temp_require_port_per_spine = int(gpu_num/temp_require_spine_num)

    #         leaf_remain_empt_server_list = []
    #         for temp_leaf_id in range(self.leaf_num):
    #             leaf_remain_empt_server_list.append(0)
    #         for temp_server_id in range(self.server_num):
    #             temp_leaf_id = int(temp_server_id/self.gpu_per_leaf*self.gpu_per_server)
    #             if self.gpu_per_server in self.server_resource_manager_.server_list[temp_server_id].gpu_group:
    #                 leaf_remain_empt_server_list[temp_leaf_id] += 1
    #         allocate_success, allocation_link_mapping, leaf_occupy_gpu_num_map, spine_occupy_port_num_map, job_allocated_leaf_spine_link = self.connection_manager_.update_leaf_to_spine_map_according_to_gpu_size(gpu_num, leaf_remain_empt_server_list, temp_require_leaf_num, temp_require_spine_num)
    #         if allocate_success:
    #             chosen_gpu_list = []
    #             for chosen_leaf_id in leaf_occupy_gpu_num_map:
    #                 chosen_gpu_list.extend(self.server_resource_manager_.choose_gpu_in_one_leaf(chosen_leaf_id, leaf_occupy_gpu_num_map[chosen_leaf_id]))
    #                 self.leaf_resource_manager_.leaf_list[chosen_leaf_id].update_leaf_group_with_required_num(leaf_occupy_gpu_num_map[chosen_leaf_id])
    #             for chosen_spine_id in spine_occupy_port_num_map:
    #                 self.spine_resource_manager_.spine_list[chosen_spine_id].update_spine_group_with_required_num(spine_occupy_port_num_map[chosen_spine_id])
    #             for output_gpu_index in chosen_gpu_list:
    #                 output_leaf_index = utils.get_leaf_module_id(chosen_leaf_id, self.gpu_num)
    #                 allocation_link_mapping.append([output_gpu_index, output_leaf_index, 1])
    #                 allocation_link_mapping.append([output_leaf_index, output_gpu_index, 1])
    #             new_job.start_time = sim_time
    #             new_job.allocated_gpus = chosen_gpu_list
    #             new_job.job_allocated_leaf_spine_link = job_allocated_leaf_spine_link
    #             self.current_job_list[job_id] = new_job
    #             print("finish allocation2")
